#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int main()
{
    int n,fz;
    int i,j;
    printf("输入物品个数和背包负重（n fz）:"); 
    scanf("%d %d",&n,&fz);
    int a[n][2];//C99
 
    printf("输入重量和价值：\n"); 
    for(i = 0;i < n;i++)
    {
        scanf("%d %d",&a[i][0],&a[i][1]);
        //printf("%d %d\n",a[i][0],a[i][1]);
    }
 
    int size = (int)pow(2,n);
    int** ls = (int**)malloc(sizeof(int*)*size);//创建一个指针数组，每个元素可以指向一个int*类型 
    for(i = 0;i < size;i++)
    {
        ls[i] = (int*)malloc(sizeof(int)*n);//将每个元素指向分配的一维数组 
    }
 
    for(i = 0;i < size;i++)
    {
    	//生成集合的全部子集 
    	int t;
        for(t = i,j = n-1;j >= 0;j--)
        {
            if(t == 0)
            {
                ls[i][j] = 0;
                continue;
            }
            ls[i][j] = t % 2;
            t = t / 2;
        }
    }
 
//下面代码用于检查所有的组合，即重量组合的全部0/1标记子集 
//    for(i = 0;i < size;i++)
//    {
//        for(j = 0;j < n;j++)
//        {
//            printf("%d ",ls[i][j]);
//        }
//        puts("");
//    }
 
    int w = 0;
    int v = 0;
    int maxv = 0;
    int gw = 0;
    int flag = -1;
    for(i = 0;i < size;i++)
    {
        for(w = 0,v = 0,j = 0;j < n;j++)
        {
            if(w < fz)
            {
                if(ls[i][j] == 1)
                {
                     w = w + a[j][0];
                     v = v + a[j][1];
                }
            }
            else
            {
                break;
            }
        }
        if(maxv < v && w <= fz)
        {
            maxv = v;
            flag = i;
            gw = w;
        }
    }
    printf("重量：\t");
    for(i = 0;i < n;i++)
    {
    	printf("%-5d",a[i][0]);
    }
    puts("");
 
    printf("价值：\t");
    for(i = 0;i < n;i++)
    {
    	printf("%-5d",a[i][1]);
    }
    puts("");
 
    printf("组合：\t");
    for(i = 0;i < n;i++)
    {
    	printf("%-5d",ls[flag][i]);
    }
    printf("\n最佳重量：%d，最大价值：%d",gw,maxv);
 
    return 0;
}